#include "classical-problems.h"
#include <stdio.h>

namespace pot {
int CountOnes(int N) {
  int count = 0;
  while (N > 0) {
    if ((N % 10) == 1) ++count;
    N /= 10;
  }
  return count;
}

int NumberOfOnesNaive(int N) {
  int count = 0;
  for (int i = 1; i <= N; ++i) {
    count += CountOnes(i);
  }
  return count;
}

int NumberOfOnes(int N) {  
  int count = 0;
  int divisor = 1;
  int high_number = N;
  while (high_number > 0) {
    int d = divisor * 10;
    high_number = N / d;

    count += divisor * high_number;
    
    int current_digit = (N / divisor) % 10; 
    
    if (current_digit == 1) count += N % divisor + 1;
    else if (current_digit > 1) count += divisor;
    
    divisor = d;
  }

  return count;
}

void NumberOfOnesTest(int N) {
  int count1 = NumberOfOnes(N);
  int count2 = NumberOfOnesNaive(N);

  if (count1 != count2) {
    printf("%d: %d, %d\n", N, count1, count2);
    printf("------------------------------------\n");
  }
}

void NumberOfOnesTests(int N) {
  for (int i = 0; i < N; ++i) {
    NumberOfOnesTest(i);    
  }
}
} // pot
